/*
https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/solution/cai-zi-mi-by-leetcode-solution-345u/
 */
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1178 {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer,Integer> ever=new HashMap<>();
        for (String word : words) {
            int mask=0;
            for (char c : word.toCharArray()) {
                mask|=(1<<(c-'a'));
            }
            if (Integer.bitCount(mask)<=7){
                ever.put(mask,ever.getOrDefault(mask,0)+1);
            }
        }
        List<Integer> ans=new ArrayList<>();
        for (String puzzle : puzzles) {
            int total=0;
            int mask=0;
            for (int i=1;i<7;i++){
                mask|=(1<<puzzle.charAt(i)-'a');
            }
            int sub=mask;
            do{
                int s=sub|(1<<(puzzle.charAt(0)-'a'));
                total+=ever.getOrDefault(s,0);
                sub=(sub-1)&mask;
            }while (sub!=mask);
            ans.add(total);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1178().findNumOfValidWords(new String[]{"aaaa","asas","able","ability","actt","actor","access"},new String[]{"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"}));
    }
}
